package leetcode_900;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 *@author 周杨
 *BinaryTreesWithFactors_823 用数组A里出现的元素构造这样一棵树 每个节点等于其子树节点的乘积 问能构造多少合法的树
 *describe:用动态规划 AC 73%
 *2018年10月29日 下午2:10:56
 */
public class BinaryTreesWithFactors_823 {
	public static void main(String[] args) {
		BinaryTreesWithFactors_823 test=new BinaryTreesWithFactors_823();
		//System.out.println(test.numFactoredBinaryTrees(new int[] {2,4}));
		System.out.println(test.numFactoredBinaryTrees(new int[] {2,3,6,18}));
	}
	int MOD=1000000007;
	public int numFactoredBinaryTrees(int[] A) {
        Arrays.sort(A);
        long res=0;
        Map<Integer,Long> dp=new HashMap<Integer,Long>();
        for(int i=0;i<A.length;++i) {
        	long count=1;
        	for(int j=0;j<i;++j) {
        		if(A[i]%A[j]==0&&dp.containsKey(A[i]/A[j])) {
        			count+=dp.get(A[j])*dp.get(A[i]/A[j]);
        			count=(count+MOD)%MOD;
        		}
        	}
        	dp.put(A[i], count);
        	res=((count+res+MOD)%MOD);
        }
        return (int)res;
    }
	
	
	/**
	 * describe:思想错误 每个元素竟然能用无数次 还是看错了 节点不允许出现A里没有的值
	 * 2018年10月29日 下午1:11:31
	 */
	public int numFactoredBinaryTrees1(int[] A) {
        Arrays.sort(A);
        int res=0;
        Map<Integer,Integer> dp=new HashMap<Integer,Integer>();
        for(int i=0;i<A.length;++i) {
        	int count=1;
        	for(int j=0;j<i;++j) {
        		if(A[i]%A[j]==0&&dp.containsKey(A[i]/A[j])) {
        			count+=dp.get(A[i]/A[j]);
        		}
        	}
        	dp.put(A[i], count);
        	res+=count;
        }
        return res;
    }
	
}
